package Offer;
/*
* 二叉搜索树变双向链表
*
* */

public class Offer36treeToDoublyList {
    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val,Node _left,Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }


    Node first=new Node(Integer.MAX_VALUE);
    Node tail=new Node(Integer.MIN_VALUE);
    Node pre=new Node();
    public Node treeToDoublyList(Node root) {
        if(root==null){
            return root;
        }
        dfs(root);
        first.left=tail;
        tail.right=first;
        return first;
    }

    private void dfs(Node root) {
        if(root==null){
            return;
        }
        dfs(root.left);
        pre.right=root;
        root.left=pre;
        pre=root;
        //定位首位节点
        if(root.val<first.val){
            first=root;
        }
        if(root.val>tail.val){
            tail=root;
        }
        dfs(root.right);
    }
}
